#include <iostream>
#include <cstring> // 为了使用memcpy函数，需要包含这个头文件

// 打印数组的函数
void PrintArr(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 归并排序的递归函数
void _mergersort(int* a, int left, int right, int* tempt)
{
	// 如果左索引不小于右索引，说明子数组只有一个元素或为空，无需排序
	if (left >= right)
		return;
	
	// 找到中间索引，将数组分为两部分
	int mid = (left + right) / 2;
	
	// 递归地对左半部分进行归并排序
	_mergersort(a, left, mid, tempt);
	
	// 递归地对右半部分进行归并排序
	_mergersort(a, mid + 1, right, tempt);

	// 合并两个已排序的子数组
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1; // i是临时数组的索引
	
	// 合并过程，比较两个子数组的元素，按顺序放入临时数组
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tempt[i++] = a[begin1++];
		}
		else
		{
			tempt[i++] = a[begin2++];
		}
	}
	
	// 将左子数组剩余的元素复制到临时数组
	while (begin1 <= end1)
	{
		tempt[i++] = a[begin1++];
	}

	// 将右子数组剩余的元素复制到临时数组
	while (begin2 <= end2)
	{
		tempt[i++] = a[begin2++];
	}

	// 将合并后的数组复制回原数组
	std::memcpy(a + left, tempt + left, sizeof(int) * (right - left + 1));
}

// 归并排序的封装函数
void MergeSort(int* a, int n)
{
	int* tempt = new int[n]; // 分配临时数组用于合并过程
	_mergersort(a, 0, n - 1, tempt); // 调用递归函数进行归并排序
	delete[] tempt; // 释放临时数组的内存
}

int main()
{
	// 初始化一个数组
	int a[] = { /* 数组元素列表，已省略以保持简洁 */ };
	
	// 打印排序前的数组
	PrintArr(a, sizeof(a) / sizeof(int));
	
	// 对数组进行归并排序
	MergeSort(a, sizeof(a) / sizeof(int));
	
	// 打印排序后的数组
	PrintArr(a, sizeof(a) / sizeof(int));
	
	return 0;
}